package leetcode;

/**
 * 226. 翻转二叉树
 * 翻转一棵二叉树。
 * 示例：
 * 输入：
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 * 输出：
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 */

public class problems_226 {

    public static void main(String[] arge) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(3);
        TreeNode A4 = new TreeNode(4);
        TreeNode A5 = new TreeNode(5);
        TreeNode A6 = new TreeNode(6);
        TreeNode A7 = new TreeNode(7);
        TreeNode A8 = new TreeNode(8);
        TreeNode A9 = new TreeNode(9);
        A4.left = A2;
        A4.right = A7;
        A2.left = A1;
        A2.right = A3;
        A7.left = A6;
        A7.right = A9;
        A4 = new Solution().invertTree(A4);
        System.out.println();
    }
    static class Solution {
        public TreeNode invertTree(TreeNode root) {
            if(null == root) return null;
            TreeNode temp = root.right;
            root.right = root.left;
            root.left = temp;
            if(null != root.left) invertTree(root.left);
            if(null != root.right) invertTree(root.right);
            return root;
        }
    }
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
